package graph.search;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

public class DFS {

	public static ArrayList<Node> listN = new ArrayList<Node>();
	public static ArrayList<Node> listVisited = new ArrayList<Node>();
	public static HashMap<Integer, ArrayList<Node>> listPath = new HashMap<Integer, ArrayList<Node>>();
	public static Node rootNode;
	public static Node targetNode;

	/**
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {

		
		//GetInfo("/home/quyet/test/sharedQuyet/01id1500.txt", "1973");
		
		LoadData("/home/quyet/test/data1000/nodes.txt");
		LoadDataTung("/home/quyet/test/sharedQuyet/01id1500.txt");

		listVisited = new ArrayList<Node>();
		int id = listN.indexOf(new Node("1775"));
		rootNode = listN.get(id);
		int idt = listN.indexOf(new Node("1783"));
		targetNode = listN.get(idt);
		// Run DFSl
		// run();

		ArrayList<String> listPath = findPath(rootNode, targetNode);
		for (String p : listPath)
			System.out.println(p);

	}

	public static ArrayList<String> findPath(Node s, Node t) {
		
		int ids = listN.indexOf(s);		
		
		if (listN.get(ids).visited)
			return listN.get(ids).listPath;
		
		listN.get(ids).visited = true;
		
		if (listN.get(ids).equals(t))
			listN.get(ids).listPath.add(t.id);
		else {			
			listN.get(ids).children.remove(s);

			for (Node child : listN.get(ids).children) {				
					child.listPath = findPath(child, t);
					for (String p : child.listPath)
						listN.get(ids).listPath.add(s.id + " -> " + p);	
			}
		}		

		return listN.get(ids).listPath;
	}

	//
	public static void run() {
		// DFS uses Stack data structure
		Stack<Node> s = new Stack<Node>();
		s.push(rootNode);
		rootNode.visited = true;
		listVisited.add(rootNode);
		int countPath = 0;
		while (!s.isEmpty()) {
			Node n = (Node) s.peek();
			Node child = getUnvisitedChildNode(n);
			if (child != null) {
				int id = listN.indexOf(child);
				listN.get(id).visited = true;

				listVisited.add(child);
				s.push(child);

				if (child.equals(targetNode)) {
					countPath += 1;
					listPath.put(countPath, listVisited);
					listVisited.remove(child);

					for (Node cn : child.children)
						if (!cn.visited)
							cn.visited = true;

				}
			} else {
				Node m = s.pop();
				listVisited.remove(m);
			}

		}

		// for (Node n : listN) {
		// n.visited = false;
		// for (Node c : n.children)
		// c.visited = false;
		// }

	}

	public static Node getUnvisitedChildNode(Node n) {
		for (Node ni : n.children) {
			if (ni.equals(targetNode))
				return ni;
			if (!ni.visited)
				return ni;
		}
		return null;
	}

	public static ArrayList<Node> getUnvisitedListChild(Node n) {
		ArrayList<Node> list = new ArrayList<Node>();
		for (Node ni : n.children) {
			if (ni.visited)
				list.add(ni);
		}
		n.children.removeAll(list);
		return n.children;
	}
	public static void LoadDataTung(String filePath) throws IOException {
		FileReader f = new FileReader(filePath);
		BufferedReader bNode = new BufferedReader(f);

		String strLine = null;
		while ((strLine = bNode.readLine()) != null) {
			String[] node = strLine.split("\t");

			Node ni = new Node(node[0]);
			for (int i = 9; i < node.length; i++) {
				Node nj = new Node(node[i]);
				ni.children.add(nj);
				if (!listN.contains(nj))
					listN.add(nj);
			}

			if (!listN.contains(ni))
				listN.add(ni);
			else {
				if (ni.children.size() > 0) {
					int id = listN.indexOf(ni);
					listN.get(id).children = ni.children;
				}
			}
		}
		bNode.close();
	}
	
	public static void GetInfo(String filePath, String idFind) throws IOException {
		FileReader f = new FileReader(filePath);
		BufferedReader bNode = new BufferedReader(f);

		String strLine = null;
		while ((strLine = bNode.readLine()) != null) {
			String[] node = strLine.split("\t");
			
			if(node[0].equals(idFind)){
				System.out.println(strLine);
				continue;
			}		
		}
		bNode.close();
	}
	
	public static void LoadData(String filePath) throws IOException {
		FileReader f = new FileReader(filePath);
		BufferedReader bNode = new BufferedReader(f);

		String strLine = null;
		while ((strLine = bNode.readLine()) != null) {
			String[] node = strLine.split("\t");

			Node ni = new Node(node[0]);
			for (int i = 3; i < node.length; i++) {
				Node nj = new Node(node[i]);
				ni.children.add(nj);
				if (!listN.contains(nj))
					listN.add(nj);
			}

			if (!listN.contains(ni))
				listN.add(ni);
			else {
				int id = listN.indexOf(ni);
				listN.get(id).children = ni.children;
			}
		}
		bNode.close();
	}

}